package easy;

/**
 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
 * 说明：本题中，我们将空字符串定义为有效的回文串。
 *
 *  示例 1:
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 * 解释："amanaplanacanalpanama" 是回文串
 *
 *  示例 2:
 * 输入: "race a car"
 * 输出: false
 * 解释："raceacar" 不是回文串
 *
 *  提示：
 *  1 <= s.length <= 2 * 105 
 *  字符串 s 由 ASCII 字符组成 
 *  
 *  Related Topics 双指针 字符串 
 *  👍 437 👎 0
 */

import java.util.ArrayDeque;

public class L125_验证回文串 {
    public static void main(String[] args) {
        System.out.println(new L125_验证回文串().isPalindrome3("A man, a plan, a canal: Panama"));
    }

    /**
     * String API.
     *
     * 解答成功:
     * 执行耗时:32 ms,击败了5.58% 的Java用户
     * 内存消耗:39.8 MB,击败了5.08% 的Java用户
     */
    public boolean isPalindrome(String s) {
        if (s == null || s.equals("")) return true;
        s = s.replaceAll("((?![a-zA-Z0-9]).)*", "aVa").toLowerCase();
        return s.equals(new StringBuilder(s).reverse().toString());
    }

    /**
     * 双指针.
     *
     * 解答成功:
     * 执行耗时:2 ms,击败了97.78% 的Java用户
     * 内存消耗:38.6 MB,击败了29.52% 的Java用户
     */
    public boolean isPalindrome2(String s) {
        if (s == null || s.equals("")) return true;

        char[] charArr = s.toLowerCase().toCharArray();
        int left = 0;
        int right = charArr.length - 1;
        while (left <= right) {
            while (left < right && !isValidChar(charArr[left])) {
                left++;
            }
            while (left < right && !isValidChar(charArr[right])) {
                right--;
            }
            if (charArr[left] == charArr[right]){
                left++;
                right--;
            } else {
                return false;
            }
        }

        return true;
    }

    /**
     * 栈.
     *
     * 解答成功:
     * 执行耗时:5 ms,击败了29.14% 的Java用户
     * 内存消耗:38.2 MB,击败了91.44% 的Java用户
     */
    public boolean isPalindrome3(String s) {
        if (s == null || s.equals("")) return true;

        s = s.toLowerCase();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        char[] charArr = s.toCharArray();

        for (char c: charArr) {
            if (isValidChar(c)){
                stack.addLast(c);
            }
        }

        for (int i = 0; i < charArr.length; i++) {
            if (isValidChar(charArr[i])) {
                if (stack.removeLast() != charArr[i]) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValidChar(char c) {
        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {
            return true;
        } else {
            return false;
        }
    }
}
